package org.itboys.seller.utils;

import com.alibaba.fastjson.JSON;
import com.google.common.collect.Lists;
import org.itboys.seller.dto.InfoMatchBO;
import org.itboys.seller.meta.InfoPublish;

import java.util.List;

/**
 * 匹配算法
 * Created by weisky on 2016/10/24.
 */
public class MatchingUtils {

    /**
     * 开始匹配
     * @param list：需要遍历的目标集合(注意：目标集合必须是冒泡排序后的结果)
     * @param sum：固定值
     * @return
     */
    public static List<Integer> start(List<InfoPublish> list, int sum) {
        List<Integer> findNumIndex = Lists.newArrayList();
        boolean flag = true;
        boolean result = false;
        int length = list.size();
        for(int i = 0; i < length; i++){
            int mix = list.get(0).getAmount();// 当前最小值
            int max = list.get(list.size() - 1).getAmount();// 当前最大值
            if (max == sum) {// 找到等于“和”的元素,打个标记
                findNumIndex.add(list.size() - 1);
                result = true;
                break;
            }
            if (mix + max > sum && flag) {// 删除没用的最大值
                list.remove(list.size() - 1);
            } else {
                break;
            }
        }

        if(result){//集合存在和目标值相等的数  返回集合下标
            return findNumIndex;
        }

        //集合中不存在相等的值 开始递归计算
        List<Integer> result2 = startMath(list, sum, findNumIndex);
        return result2;
    }

    /**
     * 开始匹配
     * @param list
     * @param sum
     */
    private static List<Integer> startMath(List<InfoPublish> list, int sum,  List<Integer> findNumIndex) {
        for (int i = 0; i <= list.size() - 2; i++) {
            findNumIndex.clear();
            findNumIndex.add(list.size() - 1 - i);// 记录第一个元素坐标
            int indexNum = list.get(list.size() - 1 - i).getAmount();// 从最大的元素开始，依次往前推
            boolean result = action(list, indexNum, list.size() - 1 - i, sum, findNumIndex);
            if(result){
                break;
            }
        }
        Integer temp = 0;
        for (Integer i : findNumIndex){
            temp += list.get(i).getAmount();
        }
        if(temp != sum){
            findNumIndex.clear();
        }
        return findNumIndex;
    }

    /**
     * 递归方法
     * @param list 被查询的数组
     * @param indexsum 当前元素相加的和
     * @param index 下一个元素位置
     * @param sum 要匹配的和
     */
    private static boolean action(List<InfoPublish> list, int indexsum, int index, int sum, List<Integer> findNumIndex) {
        if (index == 0)
            return false;
        if (indexsum + list.get(index - 1).getAmount() > sum) {// 元素【index-1】太大了，跳到下一个元素继续遍历
            action(list, indexsum, index - 1, sum, findNumIndex);
        } else if (indexsum + list.get(index - 1).getAmount() < sum) {// 元素【index-1】可能符合条件，继续往下找
            findNumIndex.add(index - 1);// 记录此元素坐标
            indexsum = indexsum + list.get(index - 1).getAmount();// 更新元素的和
            action(list, indexsum, index - 1, sum, findNumIndex);
        } else if (indexsum + list.get(index - 1).getAmount() == sum) {
            findNumIndex.add(index - 1);
            System.out.println("相加等于" + sum + "的数组元素下标为:"+ JSON.toJSONString(findNumIndex));
            System.out.println("相加等于" + sum + "的数组为：");
            for (int a : findNumIndex) {
                System.out.println(list.get(a));
            }
            System.out.println("-----------------------");
            return true;//告诉系统找到了
        }
        return true;
    }

    public static void main(String[] args) {

        //List<Integer> list = Lists.newArrayList(2,6,8,12,13,14,15,19,20,30,40,60,80,81,82,83,84,85,86,87,101);
        //List<Integer> findNumIndex = MatchingUtils.start(list, 100);
        //System.out.println("符合目标的集合下标为："+JSON.toJSONString(findNumIndex));
        //for (Integer i : findNumIndex){
        //    System.out.println("集合值为："+list.get(i));
        //}

    }
}
